' Written by Craig'n'Dave
Module Module1
    ' Hash table using an array
    Function hashing_function(item As String, table_size As Integer)
        ' Simple hashing algorithm adds ascii values of characters modulus table size
        Dim total As Integer = 0
        For character = 1 To Len(item)
            total = total + Asc(Mid(item, character, 1))
        Next
        Return total Mod table_size
    End Function

    Function create_hash_table(items As Array, table_size As Integer)
        ' Reserve memory for hashing table
        Dim hash_table(table_size) As String
        Dim h As Integer
        ' Place data in hashing table
        For index = 0 To items.Length - 1
            h = hashing_function(items(index), table_size)
            If hash_table(h) <> "" Then
                Console.WriteLine("Collision inserting " & items(index) & " at " & h)
                ' On collision insert in next available space
                Do While hash_table(h) <> ""
                    h = h + 1
                Loop
            End If
            hash_table(h) = items(index)
            Console.WriteLine("Inserted " & items(index) & " at position " & h)
        Next
        Return hash_table
    End Function

    Sub search_hash_table(item_to_find As String, hash_table As Array)
        Dim found As Boolean = False
        Dim h As Integer
        h = hashing_function(item_to_find, (hash_table.Length - 1))
        ' Attempt to find item at hash value
        If hash_table(h) <> "" Then
            If hash_table(h) = item_to_find Then
                found = True
            Else
                ' Degrade to linear search for collisions
                Do While h < hash_table.Length And Not found
                    If hash_table(h) <> item_to_find Then
                        h = h + 1
                    Else
                        found = True
                    End If
                Loop
            End If
        End If
        If found Then
            Console.WriteLine("Item found at position " & h)
        Else
            Console.WriteLine("Item not found")
        End If
    End Sub

    ' Main program starts here
    Sub Main()
        Dim items() As String = {"Florida", "Georgia", "Delaware", "Alabama", "California"}
        ' The larger the table the fewer collisions
        Dim table_size As Integer = 10
        Dim hash_table(table_size) As String
        Dim item_to_find As String
        hash_table = create_hash_table(items, table_size)
        Console.Write("Enter the state to find: ")
        item_to_find = Console.ReadLine
        search_hash_table(item_to_find, hash_table)
    End Sub
End Module
